mur mur一下...
才剛到公司一週，收到的OKR就是什麼幫前端自動產生測試用例。
前端這種一堆客製化的行為操作...怎產生啊...
來寫離職信好了(X

抱怨完後 繼續刷題~

Edit Distance

Q: https://leetcode.com/problems/edit-distance/description/

class Solution {
    Integer memo[][];

    public int minDistance(String word1, String word2) {
        memo = new Integer[word1.length() + 1][word2.length() + 1];
        return minDistanceRecur(word1, word2, word1.length(), word2.length());
    }

    int minDistanceRecur(String word1, String word2, int word1Index, int word2Index) {
        if (word1Index == 0) {
            return word2Index;
        }
        if (word2Index == 0) {
            return word1Index;
        }
        if (memo[word1Index][word2Index] != null) {
            return memo[word1Index][word2Index];
        }
        int minEditDistance = 0;
        if (word1.charAt(word1Index - 1) == word2.charAt(word2Index - 1)) {
            minEditDistance = minDistanceRecur(word1, word2, word1Index - 1, word2Index - 1);
        }
        else {
            int insertOperation = minDistanceRecur(word1, word2, word1Index, word2Index - 1);
            int deleteOperation = minDistanceRecur(word1, word2, word1Index - 1, word2Index);
            int replaceOperation = minDistanceRecur(word1, word2, word1Index - 1, word2Index - 1);
            minEditDistance = Math.min(insertOperation, Math.min(deleteOperation, replaceOperation)) + 1;
        }
        memo[word1Index][word2Index] = minEditDistance;
        return minEditDistance;
    }
}

tips: compare string, use memo[s1.length][s2.length] and start from back

Maximal Square

Q: https://leetcode.com/problems/maximal-square/description/

class Solution {
    public int maximalSquare(char[][] matrix) {
        int max = 0;
        int[][] squareCount = new int[matrix.length][matrix[0].length];
        for (int i = 0;i < matrix.length;i++) {
            for (int j = 0;j < matrix[i].length;j++) {
                if (matrix[i][j] == '0') {
                    squareCount[i][j] = 0;
                } else {
                    if (i == 0 || j == 0) {
                        squareCount[i][j] = 1;
                    } else {
                        if (squareCount[i-1][j] != 0 
                            && squareCount[i][j-1] != 0 
                            && squareCount[i-1][j-1] != 0 ) {
                            squareCount[i][j] = Math.min(squareCount[i-1][j-1], Math.min(squareCount[i-1][j], squareCount[i][j-1])) + 1;
                        } else {
                            squareCount[i][j] = 1;
                        }
                    }
                }
                max = Math.max(max, squareCount[i][j]);
            }
        }
        for (int i = 0; i < squareCount.length;i++) {
            System.out.println(Arrays.toString(squareCount[i]));
        }
        
        return max * max;
    }
}